package algorithm.unionfind;

import algorithm.unionfind.general.UnionFind;
import algorithm.unionfind.general.Student;
import utils.Asserts;
import utils.Times;

/**
 * @Description:
 * @Author Ammar
 * @Create 2023/5/17 15:11
 */
public class Test {
    static final int count = 2000000;

    public static void main(String[] args) {
//		testTime(new QuickFind(count));
//		testTime(new QuickUnion(count));
		testTime(new QuickUnion_size(count));
		testTime(new QuickUnion_rank(count));
        testTime(new QuickUnion_rank_compression(count));
        testTime(new QuickUnion_rank_spliting(count));
        testTime(new QuickUnion_rank_halving(count));
        testTime(new UnionFind<Integer>());

		UnionFind<Student> uf = new UnionFind<>();
		Student stu1 = new Student(1, "jack");
		Student stu2 = new Student(2, "rose");
		Student stu3 = new Student(3, "jack");
		Student stu4 = new Student(4, "rose");
		uf.makeSet(stu1);
		uf.makeSet(stu2);
		uf.makeSet(stu3);
		uf.makeSet(stu4);

		uf.union(stu1, stu2);
		uf.union(stu3, stu4);

//		uf.union(stu1, stu4);

		Asserts.test(!uf.isSame(stu2, stu3));
		Asserts.test(uf.isSame(stu3, stu4));
		Asserts.test(!uf.isSame(stu1, stu3));
    }

    static void testTime(UnionFind<Integer> uf) {
        for (int i = 0; i < count; i++) {
            uf.makeSet(i);
        }

        uf.union(0, 1);
        uf.union(0, 3);
        uf.union(0, 4);
        uf.union(2, 3);
        uf.union(2, 5);

        uf.union(6, 7);

        uf.union(8, 10);
        uf.union(9, 10);
        uf.union(9, 11);

        Asserts.test(!uf.isSame(2, 7));

        uf.union(4, 6);

        Asserts.test(uf.isSame(2, 7));

        Times.test(uf.getClass().getSimpleName(), () -> {
            for (int i = 0; i < count; i++) {
                uf.union((int)(Math.random() * count),
                        (int)(Math.random() * count));
            }

            for (int i = 0; i < count; i++) {
                uf.isSame((int)(Math.random() * count),
                        (int)(Math.random() * count));
            }
        });
    }

    static void testTime(AbstractUnionFind uf) {
        uf.union(0, 1);
        uf.union(0, 3);
        uf.union(0, 4);
        uf.union(2, 3);
        uf.union(2, 5);

        uf.union(6, 7);

        uf.union(8, 10);
        uf.union(9, 10);
        uf.union(9, 11);

        Asserts.test(!uf.isSame(2, 7));

        uf.union(4, 6);

        Asserts.test(uf.isSame(2, 7));

        Times.test(uf.getClass().getSimpleName(), () -> {
            for (int i = 0; i < count; i++) {
                uf.union((int)(Math.random() * count),
                        (int)(Math.random() * count));
            }

            for (int i = 0; i < count; i++) {
                uf.isSame((int)(Math.random() * count),
                        (int)(Math.random() * count));
            }
        });
    }
}
